//
//  ProblemOffer60.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/26.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 60. n个骰子的点数
 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
 示例 1:
     输入: 1
     输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
 示例 2:
     输入: 2
     输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
 限制：1 <= n <= 11
 */
@objcMembers class ProblemOffer60: NSObject {
    func solution() {
        print(dicesProbability(1))
        print(dicesProbability(2))
//        print(dicesProbability(3))
    }
    
    /*
     有n个骰子，那么能够抛出的数组种类就是 [n ~ 6*n]; 例如：只有1个骰子 [1 ~ 6], 2个[2~12]
     我们拿n=1来举例，我们求的就是[1~6]这里每一个数出现的概率, 例如：
     1> 1、2、3、4、5、6 每一个概率都是 1/6 [1/6, 1/6, 1/6, 1/6, 1/6, 1/6]
     我们拿n=2来举例，我们求的就是[2~12]这里每一个数出现的概率, 例如：
     例如：第一个骰子是1时，他的概率是1/6；第二个勺子有6种可能性，组合起来就是 2 3 4 5 6 7 每一个概率都是1/6*1/6
     由此可以使用动态规划：
     1: 计算出n-1时，每个数字出现的概率：dp[len]  len = 6 * (n-1) + 1
     2: 来了一个骰子，那么dp每一个数组，都6种变化 => dp[i] 有6种新，dp[i + (1~6)] += dp[i] * 1/6
     
     */
    func dicesProbability(_ n: Int) -> [Double] {
        var dp:[Double] = Array(repeating: 0, count: 6 * n + 1)
        for i in 1...6 {
            dp[i] = 1/6
        }
        
        if (n >= 2) {
            for i in 1...n-1 {
                var temp:[Double] = Array(repeating: 0, count: 6*(i+1)+1)
                for k in 1...6*i {
                    for j in 1...6 {
                        temp[k + j] += dp[k] * 1/6
                    }
                }
                for i in 0..<temp.count {
                    dp[i] = temp[i]
                }
            }
        }

        return Array(dp[n...6*n])
    }
}
